class Solution:
	# @param dungeon, a list of lists of integers
	# @return a integer
	def calculateMinimumHP(self, dungeon):
		row, col = len(dungeon), len(dungeon[0])
		dp = [[0 for i in xrange(col)] for x in xrange(row)]
		dp[row-1][col-1] = 1
		for i in xrange(row-2, -1, -1):
			dp[i][col-1] = max(1, dp[i+1][col-1]-dungeon[i+1][col-1])
		for j in xrange(col-2, -1, -1):
			dp[row-1][j] = max(1, dp[row-1][j+1]-dungeon[row-1][j+1])
		for i in xrange(row-2, -1, -1):
			for j in xrange(col-2, -1, -1):
				dp[i][j] = min(max(1, dp[i+1][j]-dungeon[i+1][j]), max(1, dp[i][j+1]-dungeon[i][j+1]))
		#print dp
		return max(1, dp[0][0]-dungeon[0][0])

if __name__ == '__main__':
	so = Solution()
	dun = [
		[0],
		[0]
	]
	print so.calculateMinimumHP(dun)